An interconnection network serves as a pathway for messages to travel amongst nodes of a data processing system. The messages that are sent over the interconnection network often include both data and synchronization information. The nodes of the interconnection network are typically data processing elements such as memory units or processing units. Such nodes may assume either one of two roles with respect to messages. First, they may act as switches that direct messages to their destinations. Second, they may act as message originators that originate messages which are forwarded to other nodes.
Interconnection networks are generally classified by topology, routing and flow control. The topology of an interconnection network concerns the physical arrangement of its nodes and channels into a graph. The routing strategy of an interconnection network, in contrast, refers to the strategy for creating paths in the network having a given topology. Lastly, flow control relates to the allocation of channel and buffer resources as messages travel along the paths of the interconnection network.
A topology of interconnection networks that has proven especially promising is the k-ary n-cube. A k-ary n-cube is an interconnection network that has k nodes in each of its n dimensions. An example of a k-ary n-cube is a 4.times.4 grid of nodes wherein each node is coupled to its immediately adjacent neighbors. Such a grid constitutes a 4-ary 2-cube because there are 4 nodes in each of the 2 dimensions. The k in the term "k-ary" is known as the radix. An extreme example of a k-ary n-cube is a hypercube.
Latency and throughput serve as useful benchmarks for measuring performance of an interconnection network. The latency of a message is the elapsed time from when a message send is initiated until the message is completely received. The latency of an interconnection network is the average message latency for a given set of specified conditions. Network latency can be broken down into several components. In particular, network latency is comprised of the latency attributable to nodes of the interconnection network, the latency attributable to the wires and the latency attributable to the message length. Network throughput, on the other hand, is the number of messages a network can deliver per a unit of time.